package vip.youngboy.graph;

import java.util.ArrayList;
import java.util.List;

public class Ring2 {
    /**
     * 2-3
     * 0-2,1
     * 1-3
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] order = new Solution2().findOrder(4, new int[][]{new int[]{3,2}, new int[]{2,0},new int[]{3,1},new int[]{1, 0}});
        for (int i : order) {
            System.out.println(i);
        }
    }
}


class Solution2 {

    //图
    List<List<Integer>> graph;
    //记录访问的节点避免重复
    int[] visited;

    //控制变量用于控制找到了提前返回
    boolean isValid=true;

    //结果数组
    int[] result;

    //索引
    int index;

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        //初始化图数据结构
        graph = new ArrayList<>();
        for(int i=0;i<numCourses;i++){
            graph.add(new ArrayList<Integer>());
        }
        visited=new int[numCourses];
        result=new int[numCourses];
        index=numCourses-1;
        //构建图数据结构
        for(int[] course:prerequisites){
            //确定图的方向 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。  bi->ai
            graph.get(course[1]).add(course[0]);
        }

        //深度遍历图
        for(int i=0;i<numCourses&&isValid;i++){
            if(visited[i]==0){
                dfs(i);
            }
        }

        if(!isValid){
            return new int[0];
        }

        return result;

    }


    public void dfs(int n){
        //做选择
        visited[n]=1;

        for(Integer item:graph.get(n)){
            if(visited[item]==0){
                dfs(item);
                if(!isValid){
                    //提前退出，避免重复计算
                    return;
                }
            }else if(visited[item]==1){
                //重复，说明有环
                isValid=false;
                return;
            }
        }

        //撤销选择
        visited[n]=2;
        result[index--]=n;
    }

}